/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  // 获取三角形的行数
  const n = triangle.length;

  // 初始化dp数组，使用最后一行作为初始值
  // 这样可以将空间复杂度优化到O(n)
  let dp = [...triangle[n - 1]];

  // 从倒数第二行开始向上计算
  for (let i = n - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      // 当前位置的最小路径和 = 当前值 + 下一行相邻两个位置中较小的路径和
      dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
    }
  }

  // 最终顶部的dp[0]就是最小路径和
  return dp[0];
};

// 测试案例
console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])); // 输出: 11
console.log(minimumTotal([[-10]])); // 输出: -10
